#include <iostream>
#include <string>
#include <vector>

using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(): val(0), next(nullptr) {}
    ListNode(int value): val(value), next(nullptr) {}
    ListNode(int value, ListNode* node_pointer): val(value), next(node_pointer) {}
};


class Solution {
public:
    void reorderList(ListNode* head) {

        if (head == nullptr) return;

        ListNode* tmp = head;
        vector<ListNode*> vec;
        while (tmp != nullptr) {
            vec.emplace_back(tmp);
            tmp = tmp->next;
        }

        int i = 0;
        int j = vec.size() - 1;
        while (i < j)
        {
            vec[i]->next = vec[j];
            i++;
            if (i == j) break;
            vec[j]->next = vec[i];
            j--;
        }
        vec[i] ->next = nullptr;
        

    }
};